import java.util.Arrays;

public class UnionFindSet {
    public  int[] elem;
    public UnionFindSet(int x) {
        this.elem = new int[x];
        Arrays.fill(elem,-1); // 全部赋值成负一
    }
    /**
     * 查找数据X的根节点
     * @param x
     * @return 下标
     */
    public int findRoot(int x) {
        if(x < 0) {
            throw new IndexOutOfBoundsException("下标不合法");
        }
        // 查找根节点
        while(elem[x] >= 0) {
            x = elem[x];
        }
        return x;
    }
    /**
     * 查询x1和x2 是不是同一个集合
     * @param x1
     * @param x2
     * @return
     */
    public boolean isSameUnionFindSet(int x1,int x2) {
        // 保证两个都是根节点
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);
        if(index1 == index2) {
            return true;
        }
        return false;
    }
    /**
     * 这是合并操作
     * @param x1
     * @param x2
     */
    public void union(int x1,int x2) {
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);
        if(index1 == index2) {
            // 两个已经是同一个集合了，无需再合并了
            return ;
        }
        elem[index1] = elem[index1] + elem[index2];
        elem[index2] = index1;
    }
    /**
     * 返回组合个数
     * @return
     */
    public int getCount() {
        int count = 0;
        for(int x:elem) {
            if(x < 0) {
                count++;
            }
        }
        return count;
    }
    /**
     * 打印元素
     */
    public void print() {
        for(int x:elem) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}
